class Solution {
public:

    struct Node {
      int r, c, b;
    };

    vector<vector<bool> > row;
    vector<vector<bool> > col;
    vector<vector<bool> > block;


    bool isValidSudoku(vector<vector<char> > &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        row = vector<vector<bool> >(9, vector<bool>(9, false));
        col = vector<vector<bool> >(9, vector<bool>(9, false));
        block = vector<vector<bool> >(9, vector<bool>(9, false));

        vector<Node> nodes;
        for (int i = 0; i < 9; ++i) {
          for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
              Node node;
              node.r = i;
              node.c = j;
              node.b = i / 3 * 3 + j / 3;
              nodes.push_back(node);
            } else {
              int val = board[i][j] - '1';

              if (row[i][val] || col[j][val] || block[i / 3 * 3 + j / 3][val]) {
                return false;
              }
              row[i][board[i][j] - '1'] = true;
              col[j][board[i][j] - '1'] = true;
              block[i / 3 * 3 + j / 3][board[i][j] - '1'] = true;
            }
          }
        }
        return true;


    }

    bool dfs(vector<vector<char> > &board, vector<Node> &nodes, int depth) {
      if (depth == nodes.size()) {
        return true;
      }
      int r = nodes[depth].r;
      int c = nodes[depth].c;
      int b = nodes[depth].b;

      for (int i = 0; i < 9; ++i) {
        if (row[r][i] || col[c][i] || block[b][i]) {
          continue;
        }
        row[r][i] = col[c][i] = block[b][i] = true;
        board[r][c] = static_cast<char>(i + '1');
        if (dfs(board, nodes, depth + 1)) {
          return true;
        }
        row[r][i] = col[c][i] = block[b][i] = false;
      }
      return false;
    }


};
